\subsection{Inserting and rebalancing iteratively}\label{s:315}

We proved in Section~\ref{s:complexity} the existence of a 2-approximation algorithm for maximin support that runs in time $O(\bal\cdot |C|\cdot k)$ or $O(\bal\cdot |C|)$ (Theorems \ref{thm:mms} and \ref{thm:2eps} respectively). 
We use now our heuristic to develop $\phragmms$, a $3.15$-approximation algorithm that runs in time $O(\bal\cdot k)$, and satisfies PJR as well. 
We highlight that this is the fastest known election rule to achieve a constant-factor guarantee for maximin support, and that gains in speed are of paramount importance for our blockchain application, where there are hundreds of candidates and a large number of voters.

$\phragmms$ (Algorithm~\ref{alg:balanced}) is an iterative greedy algorithm that starts with an empty committee and alternates between inserting a new candidate with the new heuristic, and fully rebalancing the weight vector, i.e., replacing it with a balanced one. This constitutes a middle ground between the approach in $\phragmen$ where a balanced vector is never computed, and the approach in $\MMS$ where $O(|C|)$ balanced vectors are computed per iteration. 
We formalize the procedure below. Notice that running the Insert procedure (Algorithm~\ref{alg:ins}) before rebalancing is optional, but the step simplifies the analysis and may provide a good starting point to the balancing algorithm.

\begin{algorithm}[htb]
\SetAlgoLined
\KwData{Approval graph $G=(N\cup C, E)$, vector $s$ of vote strengths, committee size $k$.}
Initialize $A=\emptyset$\ and $w=0\in\R^E$\;
\For{$i$ from $1$ to $k$}{
Let $(c_{\max},t_{\max})\leftarrow \maxscore(A,w)$ \; 
\tcp{candidate w.~highest score, and its score} 
Update $(A,w)\leftarrow \ins(A,w,c_{\max},t_{\max})$ \; 
\tcp{or optionally just update $A\leftarrow A+c_{\max}$} 
Replace $w$ with a balanced weight vector for $A$\;
}
\Return $(A,w)$\;
\caption{$\phragmms$}
\label{alg:balanced}
\end{algorithm}

\begin{theorem}\label{thm:315}
$\phragmms$ offers a $3.15$-approximation guarantee for the maximin support problem, satisfies the PJR property, and executes in time $O(\bal\cdot k)$, assuming that $\bal= \Omega(|E|\cdot \log k)$.
\end{theorem}

This in turn proves Theorem~\ref{thm:intro1}. 
The claim on runtime is straightforward: we established in Theorem~\ref{thm:runtimes} that $\maxscore$ runs in time $O(|E|\cdot \log k)$, so each iteration of $\phragmms$ has a runtime of $O(|E|\cdot \log k + \bal)=O(\bal)$, assuming that $\bal= \Omega(|E|\cdot \log k)$. 
In fact, in Appendix~\ref{s:algorithms} we improve upon this analysis and show how each iteration can run in time $O(|E| + \bal)$.
Next, in order to prove the PJR property we need the following technical lemmas.

\begin{lemma}\label{lem:2balanced}
If $(A,w)$ and $(A',w')$ are two balanced partial solutions with $A\subseteq A'$, then $\supp_w(c) \geq \supp_{w'}(c)$ for each $c\in A$, and $\score_{(A,w)}(c')\geq \score_{(A',w')}(c')$ for each $c'\in C\setminus A'$.
\end{lemma}

\begin{lemma}\label{lem:localopt}
If $\supp_w(A)\geq \max_{c'\in C\setminus A} \score(c')$ holds for a full solution $(A,w)$, then $A$ satisfies PJR.
\end{lemma}

Lemma \ref{lem:2balanced} formalizes the intuition that as more candidates are added to a partial solution that is kept balanced, the scores of unelected candidates may only decrease, never increase; its proof is delayed to Appendix~\ref{s:proofs}.
Lemma~\ref{lem:localopt} establishes the key connection that exists between our definition of score -- and by extension our heuristic -- and the PJR property, and its proof is delayed to the end of Section~\ref{s:local}. 
We prove now that the output of $\phragmms$ satisfies the condition in Lemma~\ref{lem:localopt}, and hence satisfies PJR.

\begin{lemma}\label{lem:315localoptimality}
At the end of each one of the $k$ iterations of Algorithm $\phragmms$, if $(A,w)$ is the current partial balanced solution, we have that $\supp_{w}(A)\geq \max_{c'\in C\setminus A} \score_{(A,w)}(c')$.
\end{lemma}
\begin{proof}
Let $(A_i,w_i)$ be the partial solution at the end of the $i$-th iteration. We prove the claim by induction on $i$, with the base case $i=0$ being trivial as we use the convention that $\supp_{w_0}(\emptyset)=\infty$ for any $w_0$. For $i\geq 1$, suppose that on iteration $i$ we insert a candidate $c_i$ with highest score, and let $w'$ be the vector that is output by $\ins(A_{i-1}, w_{i-1}, c_i, \score_{(A_{i-1}, w_{i-1})}(c_i))$ (Algorithm~\ref{alg:ins}). Then

\begin{align*}
\supp_{w_i}(A_i) &\geq \supp_{w'}(A_i) \\
&\geq \min\{ \supp_{w_{i-1}}(A_{i-1}), \score_{(A_{i-1}, w_{i-1})}(c_i) \} \\
&\geq \max_{c'\in C\setminus A_{i-1}} \score_{(A_{i-1}, w_{i-1})}(c') \\
&\geq \max_{c'\in C\setminus A_{i}} \score_{(A_{i}, w_{i})}(c'), 
\end{align*}
%
where the first inequality holds as $w_i$ is balanced for $A_i$, the second one is a property of our heuristic, the third one holds by induction hypothesis and the choice of candidate $c_i$, and the last one follows from Lemma~\ref{lem:2balanced}. 
This completes the proof.
\end{proof}


It remains to prove the claimed approximation guarantee for $\phragmms$. 
To do that, we use the following key technical result, whose proof is based on the flow decomposition theorem and is delayed to Apendix~\ref{s:flow}. 
This result says that if a partial solution is balanced, then not only are there unelected candidates that can be appended with high support, but they also have large scores, so we can find them efficiently with our heuristic. 
More specifically, there must be a subset of voters with large aggregate vote strength who currently have too few representatives, so these representatives all have large supports, and in turn the voters have large slack. 

\begin{lemma}\label{lem:N_a}
If $(A^*, w^*)$ is an optimal solution to the maximin support instance with $t^*=\supp_{w^*}(A^*)$, and $(A,w)$ is a balanced solution with $|A|\leq k$ and $A\neq A^*$, then for each $0\leq a\leq 1$ there is a subset $N(a)\subseteq N$ of voters such that 
\begin{enumerate}
	\item each voter $n\in N(a)$ approves of a candidate in $A^*\setminus A$;
	\item for each voter $n\in N(a)$, we have $\supp_w(A\cap C_n)\geq at^*$;
	\item $\sum_{n\in N(a)} s_n \geq |A^* \setminus A|\cdot (1-a) t^*$; and
	\item for any $b$ with $a\leq b\leq 1$ we have that $N(b)\subseteq N(a)$, and a voter $n\in N(a)$ belongs to $N(b)$ if and only if $n$ observes property 2 above with parameter $a$ replaced by $b$.
\end{enumerate}
\end{lemma}

As a warm-up, we show how this last result easily implies a $4$-approximation guarantee for $\phragmms$.

\begin{lemma}
If $(A,w)$, $(A^*,w^*)$ and $t^*$ are as in Lemma~\ref{lem:N_a}, there is a candidate $c'\in A^*\setminus A$ with $\score(c')\geq t^*/4$. Hence, $\phragmms$ provides a $4$-approximation for the maximin support problem.
\end{lemma}

\begin{proof}
We apply Lemma~\ref{lem:N_a} with $a=1/2$. In what follows we refer to the four properties stated in that lemma. We have that

\begin{align*}
    \sum_{c'\in A^*\setminus A} \prescore(c',t^*/4) &=\sum_{c'\in A^*\setminus A} \sum_{n\in N_{c'}} \slack(n,t^*/4) \\
		&\geq \sum_{n\in N(a)} \slack(n,t^*/4) \\
    &\geq \sum_{n\in N(a)} \Big[ s_n - \frac{t^*}{4}\sum_{c\in A\cap C_n} \frac{w_{nc}}{\supp_w(c)} \Big] \\
    &\geq \sum_{n\in N(a)} \Big[ s_n - \frac{1}{2}\sum_{c\in A\cap C_n} w_{nc} \Big] \\
    &\geq \frac{1}{2}\sum_{n\in N(a)} s_n \\
		&\geq \frac{1}{2} (|A^*\setminus A|\cdot t^*/2) = |A^*\setminus A|\cdot t^*/4, 
\end{align*}
%
where the five inequalities hold respectively by property 1 (which implies $N(a)\subseteq \cup_{c'\in A^*\setminus A} N_{c'}$), by definition of slack (equation~\ref{eq:slack}), by property 2, by feasibility (inequality~\ref{eq:feasible}), and by property 3.
Therefore, by an averaging argument, there must be a candidate $c'\in A^*\setminus A$ with $\prescore(c',t^*/4)\geq t^*/4$, which in turn implies that $\score(c')\geq t^*/4$ by definition of score. 
The $4$-approximation guarantee for Algorithm $\phragmms$ easily follows by induction on the $k$ iterations, using Lemma~\ref{lem:insert} and the fact that rebalancing a partial solution never decreases its least member support.
\end{proof}

To get a better approximation guarantee for the $\phragmms$ rule and finish the proof of Theorem~\ref{thm:315}, we apply Lemma~\ref{lem:N_a} with a more carefully selected parameter $a$, and use the following technical result whose proof is delayed to Apppendix~\ref{s:proofs}.

\begin{lemma}\label{lem:Lebesgue}
Consider a strictly increasing and differentiable function $f:\mathbb{R}\rightarrow \mathbb{R}$, with a unique root $\chi$. For a finite sum $\sum_{i\in I} \alpha_i f(x_i)$ where $\alpha_i\in\mathbb{R}$ and $ x_i\geq \chi$ for each $i\in I$, we have that
$$\sum_{i\in I} \alpha_i f(x_i) = \int_{\chi}^{\infty} f'(x) \big(\sum_{i\in I: \ x_i\geq x} \alpha_i\big)dx.$$
\end{lemma}

\begin{lemma}\label{lem:candidate315}
If $(A,w)$, $(A^*,w^*)$ and $t^*$ are as in Lemma~\ref{lem:N_a}, there is a candidate $c'\in A^*\setminus A$ with $\score(c')\geq t^*/3.15$. Hence, $\phragmms$ provides a $3.15$-approximation for the maximin support problem.
\end{lemma}

\begin{proof}
We refer to Lemma~\ref{lem:N_a} and its properties, with a parameter $0\leq a\leq 1$ to be defined later. We have
\begin{align*}
    \sum_{c'\in A^*\setminus A} & \prescore(c',at^*) \\ 
		&= \sum_{c'\in A^*\setminus A} \ \sum_{n\in N_c} \slack(n, at^*) \\
		&\geq \sum_{n\in N(a)} \slack(n, at^*) \\
    &\geq \sum_{n\in N(a)} \Big[ s_n - at^* \sum_{c\in A\cap C_n} \frac{w_{nc}}{\supp_w(c)} \Big] \\
    &\geq \sum_{n\in N(a)} \Big[ s_n - \frac{at^*}{\supp_w(A\cap C_n)} \sum_{c\in A\cap C_n} w_{nc} \Big] \\
    &\geq \sum_{n\in N(a)} s_n\Big[ 1- \frac{at^*}{\supp_w(A\cap C_n)} \Big], 
\end{align*}
%
where the four inequalities hold respectively by property 1, equation~\ref{eq:slack}, property 2 and inequality~\ref{eq:feasible}, and where $\supp_w(\emptyset)=\infty$ by convention. 
At this point, we apply Lemma~\ref{lem:Lebesgue} over function $f(x):=1-a/x$, which has the unique root $\chi=a$, and index set $I=N(a)$ with $\alpha_n=s_n$ and $x_n=\supp_w(A\cap C_n)/t^*$. We obtain
\begin{align*}
    \sum_{c'\in A^*\setminus A} & \prescore(c',at^*) \\
		&\geq \int_{a}^{\infty} f'(x) \Big( \sum_{n\in N(a): \ \supp_w(A\cap C_n)\geq xt^*} s_n \Big)dx\\
    &=\int_{a}^{\infty} \frac{a}{x^2}\Big( \sum_{n\in N(x)} s_n \Big)dx \\
    &\geq \int_{a}^1 \frac{a}{x^2} \Big( |A^*\setminus A|\cdot (1-x)t^* \Big)dx \\
    & = |A^*\setminus A|\cdot at^* \int_{a}^1 \Big( \frac{1}{x^2} - \frac{1}{x} \Big)dx \\
		&= |A^*\setminus A|\cdot at^*\Big(\frac{1}{a} - 1 + \ln  a\Big),
\end{align*}
%
where we exploited properties 4 and 3. 
If we now set $a=1/3.15$, we have that $1/a - 1 + \ln a\geq 1$, so by an averaging argument there is a candidate $c'\in A^*\setminus A$ for which $\prescore(c',at^*)\geq at^*$, and hence $\score(c')\geq at^*$. The approximation guarantee for the $\phragmms$ rule follows by induction on the $k$ iterations, as before.
\end{proof}
